package com.cat.binaryTree;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/longest-zigzag-path-in-a-binary-tree/description/
 * @create 2025/9/12 15:33
 * @since JDK17
 */

public class Solution23 {
    // false : 左
    // true : 右
    int ans;

    void f(TreeNode root, boolean dir, int len) {
        ans = Math.max(ans, len);
        if (dir) {
            if (root.left != null) {
                f(root.left, false, len + 1);
            }
            if (root.right != null) {
                f(root.right, true, 1);
            }
        } else {
            if (root.right != null) {
                f(root.right, true, len + 1);
            }
            if (root.left != null) {
                f(root.left, false, 1);
            }
        }
    }

    public int longestZigZag(TreeNode root) {
        if (root == null) {
            return 0;
        }
        f(root, true, 0);
        f(root, false, 0);
        return ans;
    }
}
